| 翻訳と辞書 |
| Minimum-weight triangulation ： ウィキペディア英語版 |
Minimum-weight triangulation
In computational geometry and computer science, the minimum-weight triangulation problem is the problem of finding a triangulation of minimal total edge length.〔For surveys of the problem, see , , and .〕 That is, an input polygon or the convex hull of an input point set must be subdivided into triangles that meet edge-to-edge and vertex-to-vertex, in such a way as to minimize the sum of the perimeters of the triangles. The problem is NP-hard for point set inputs, but may be approximated to any desired degree of accuracy. For polygon inputs, it may be solved exactly in polynomial time. The minimum weight triangulation has also sometimes been called the optimal triangulation.
==History==
The problem of minimum weight triangulation of a point set was posed by , who suggested its application to the construction of triangulated irregular network models of land countours, and used a greedy heuristic to approximate it. conjectured that the minimum weight triangulation always coincided with the Delaunay triangulation, but this was quickly disproved by , and indeed showed that the weights of the two triangulations can differ by a linear factor.〔See also .〕
The minimum-weight triangulation problem became notorious when included it in a list of open problems in their book on NP-completeness, and many subsequent authors published partial results on it. Finally, showed it to be NP-hard, and showed that accurate approximations to it can be constructed efficiently.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Minimum-weight triangulation」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|